The present invention relates generally to digital processing. More particularly, the present invention relates to code generating and code sequencing. Specifically, the present invention relates to a method and apparatus for instruction re-alignment using a branch on a falsehood of a qualifying predicate.
A common operation for a digital processing system is running a program. The program code for the program is first compiled into code sequences (xe2x80x9cinstructionsxe2x80x9d), which are aligned or stored sequentially in xe2x80x9cblocksxe2x80x9d of memory. A processor processes the instructions to execute the program. For an instruction block having a conditional branch, the program control flow can either xe2x80x9cfall-throughxe2x80x9d to the next sequential instruction block or xe2x80x9cjumpxe2x80x9d to an instruction block at some offset from the instruction block having the conditional branch.
Typically, whether a conditional branch xe2x80x9cfalls-throughxe2x80x9d or xe2x80x9cjumpsxe2x80x9d is dependent on the value of a guarding predicate for the conditional branch. That is, if the guarding predicate is xe2x80x9ctruexe2x80x9d the conditional branch xe2x80x9cjumpsxe2x80x9d to a target instruction (xe2x80x9ctarget instructionxe2x80x9d) and if the guarding predicate is xe2x80x9cfalsexe2x80x9d the conditional branch xe2x80x9cfalls-throughxe2x80x9d to the next sequential instruction (xe2x80x9cfall-through instructionxe2x80x9d). Consequently, in many instances, it is necessary to re-align the target instruction with the fall through instruction in a memory without changing the original semantics of the program code (i.e., to make the original fall-through instruction the target instruction and to make the original target instruction the fall-through instruction).
FIG. 1 depicts a prior art illustration 100 of re-aligning instruction blocks. The prior art illustration 100 shows how the target instruction can be re-aligned with the fall through instruction by using a complementary predicate (i.e., pF) of a qualifying predicate (i.e., pT) to guard the conditional branch. Complementary predicates are generated by compare instructions (e.g., pT, pF=compare (a greater than b)) in which the complementary predicates have opposite logic values. For example, using the compare instruction above, if xe2x80x9caxe2x80x9d is greater than xe2x80x9cbxe2x80x9d the guarding predicate (pT) is true and its complementary predicate (pF) is false. Furthermore, if xe2x80x9caxe2x80x9d is not greater than xe2x80x9cbxe2x80x9d the guarding predicate (pT) is false and its complementary predicate (pF) is true. In the prior art, the target instruction can be re-aligned with the fall through instruction by guarding the conditional branch with the complementary predicate (pF) instead of the qualifying predicate.
Referring to FIG. 1, logical representation of code sequencing 102 represents five instructions (A through E) to be executed by a processor. Instruction A has a conditional branch for either instruction block B or C. Physical layout in memory 103 show how instructions A through E are laid out in a memory for one implementation. In the implementation of physical layout in memory 103, the conditional branch of instruction A xe2x80x9cjumpsxe2x80x9d to instruction C (xe2x80x9ctarget instructionxe2x80x9d) if the qualifying predicate (pT) is true and xe2x80x9cfalls-throughxe2x80x9d to instruction B (xe2x80x9cfall through instructionxe2x80x9d) if pT is not true.
To re-align the target instruction (instruction C) with the fall-through instruction (instruction B) in the implementation of physical layout in memory 103, the conditional branch of instruction A must be guarded by the complementary predicate (pF) of the qualifying predicate (pT). The re-aligned layout in memory 106 shows instruction A being guarded by the complementary predicate (pF) to jump to instruction B (xe2x80x9ctarget instructionxe2x80x9d) and to fall-through to instruction C (xe2x80x9cfall-through instructionxe2x80x9d) if pF is true.
A disadvantage of the prior art of re-aligning instructions is that it requires a complementary predicate for the qualifying predicate. That is, if a complementary predicate is not available for the qualifying predicate, the complementary predicate must be generated in order to re-align the instructions. Consequently, generating the complimentary predicate for a qualifying predicate can be problematic if compare instructions are complicated and cascaded. Thus, more instructions may be need to produce the complimentary predicate, which translates into additional resource usage and additional processing time.